#include "skiplist_enclave_t.h"
#include<set>
#include<random>
#include<forward_list>
#include<cstdlib>
#include<string.h>
using namespace std;
template<typename T> // 使用函数模版，T:参数化数据类型
// 跳表
class skiplist
{
    private: // 在 private 访问说明符下定义的成员只能在同一个类中访问，它们在派生类或程序的任何其他类中是不可访问的。
    // 使用50000的数据集时为16，使用10000的数据集时为14
    // static constexpr int MAX_LEVEL = 14;
    static constexpr int MAX_LEVEL = 16;
    static constexpr double P = 0.5;   //新结点出现在第二层的概率
    // 随机数产生相关，#include<random>
    std::random_device rd;
    std::mt19937 gen;
    std::uniform_real_distribution<> dis;
    struct node // 存储时每一列节点在一个node中
    // 成员表；成员函数
    {
        T data;
        node *next[MAX_LEVEL+1];
        node()
        {
            for(int i=1;i<=MAX_LEVEL;i++)
                next[i] = NULL;  //next[i]表示每个结点第i层的后继结点
        }
    };
    // 结构体变量表
    node *head;
    public:
    skiplist()
    {
        head = new node;
        gen = std::mt19937(rd()); // 生成随机数
        dis = std::uniform_real_distribution<> (0,1); // 用于从均匀分布中生成随机的浮点数，<0,1>表示取值范围的上界和下界
    }
    int randomLevel()
    {
        int ret = 1;
        while(ret<MAX_LEVEL && dis(gen)<P)
            ret++;
        return ret; // 该结点被随机到的高度
    }
    void insert(T x) //插入
    //需要将每层的新结点的前驱结点记录下来
    {
        node *tmp = new node;
        tmp->data = x;
        node *pre[MAX_LEVEL+1]; // 前驱
        node *now = head;
        int level = randomLevel();  // 新结点的层数
        for(int i=MAX_LEVEL;i>=1;i--)
        {
            while(now->next[i] != NULL && now->next[i]->data<x) now = now->next[i];
            pre[i] = now;
        }

        for(int i=level;i>=1;i--)
        {
            tmp->next[i] = pre[i]->next[i];
            pre[i]->next[i] = tmp;
        }
    }
    bool remove(T x) //删除
    // 删除成功返回true，未找到元素返回False
    {
        node *pre[MAX_LEVEL+1];
        node *now = head;
        for(int i=MAX_LEVEL;i>=1;i--)
        {
            while(now->next[i] != NULL && now->next[i]->data<x) now = now->next[i];
            pre[i] = now;
        }
        if(now->next[1] == NULL) return false;
        if(now->next[1]->data != x) return false;

        node *del = now->next[1];
        // 需要记录被删除的结点的前驱，使得每个被修改的前驱跳过被删除元素指向下一个
        // 回收内存
        for(int i=MAX_LEVEL;i>=1;i--)
        {
            if(pre[i]->next[i] != NULL && pre[i]->next[i] == del) pre[i]->next[i] = pre[i]->next[i]->next[i];
        }
        delete del;

        return true;
    }
    bool find(T x) //查找
    {
        node *now = head; //从表头开始
        for(int i=MAX_LEVEL;i>=1;i--) // 从最上面一层找起
            while(now->next[i] != NULL && now->next[i]->data<x) now = now->next[i];
        if(now->next[1] == NULL) return false;
        if(now->next[1]->data != x) return false;
        return true;
    }
};

std::set<uint32_t> S;
skiplist<uint32_t> L;
std::forward_list<uint32_t> FL;
uint32_t buf[2];

void Sinsert(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	S.insert(buf[0]);
}
void Linsert(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	L.insert(buf[0]);
}
void Finsert(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	FL.push_front(buf[0]);
	FL.sort();
}
void Sfind(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	S.find(buf[0]);
}
void Lfind(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	L.find(buf[0]);
}
void Ffind(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	std::find(FL.begin(), FL.end(), buf[0]);
}
void Sremove(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	S.erase(buf[0]);
}
void Lremove(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	L.remove(buf[0]);
}
void Fremove(uint32_t *src){
    memcpy(buf, src, sizeof buf);
	FL.remove(buf[0]);
}
